class Solution {
public:
    /**
     * @param A: an integer array
     * @return: nothing
     */
    void quickSort(vector<int> &nums, int low, int high)
    {
        if (low >= high) return; //加了这句，最后两行就不用判断了
        int start = low;
        int end = high;
        int mid = (end - start) / 2 + start;
        int pivot = nums[mid]; // 注意记录下来，不然swap操作之后nums[mid]可能变化！！
        while (start < end) //这一句必须要，要把所有能交换的都交换掉
        {
            while (nums[start] < pivot) start++;
            while (nums[end] > pivot) end--;
            if (start <= end)
            {
                swap(nums[start], nums[end]);
                start++;
                end--;
            }
        }
        quickSort(nums, low, end);
        quickSort(nums, start, high);
    }
    void sortIntegers2(vector<int> &A) {
        if (A.empty()) return;
        quickSort(A, 0, A.size() - 1);
    }
};